#define _CRT_SECURE_NO_WARNINGS 1


//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//bool Func(vector<int>& v, int k)
//{
//	int size = v.size();
//	if (size == 1)
//	{
//		return true;
//	}
//	for (int i = 0; i < size; i++)
//	{
//		for (int j = i + 1; j < size; j++)
//		{
//			if (abs(v[i] - v[j]) == k)
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//}
//
//void BackTrack(vector<vector<int>>& vv, int start, vector<int>& nums, vector<int>& temp, int k)
//{
//	vv.push_back(temp);
//	for (int i = start; i < nums.size(); i++)
//	{
//		temp.push_back(nums[i]);
//		BackTrack(vv, i + 1, nums, temp, k);
//		temp.pop_back();
//	}
//}
//
//int beautifulSubsets(vector<int>& nums, int k)
//{
//	vector<vector<int>> vv;
//	vector<int> temp;
//	BackTrack(vv, 0, nums, temp, k);
//	int count = 0;
//	for (int i = 0; i < vv.size(); i++)
//	{
//		if (Func(vv[i], k) && vv[i].size() != 0)
//		{
//			count++;
//		}
//	}
//	return count;
//}
//
//int main()
//{
//	vector<int> v = { 4,2,5,9,10,3 };
//
//	cout << beautifulSubsets(v, 1) << endl;
//
//	return 0;
//}


//#include<algorithm>
//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries)
//{
//	vector<int> v(queries.size());
//	vector<pair<int, int>> vp;
//	for (int i = 0; i < queries.size(); i++)
//	{
//		vp.push_back({ queries[i], i });
//	}
//	sort(items.begin(), items.end());
//	sort(vp.begin(), vp.end());
//	int Max = 0;
//	int begin = 0, end = 0;
//	while (begin < items.size() && end < queries.size())
//	{
//		if (items[begin][0] > vp[end].first)
//		{
//			v[vp[end].second] = Max;
//			end++;
//		}
//		else
//		{
//			Max = max(Max, items[begin][1]);
//			begin++;
//		}
//	}
//	while (end < queries.size())
//	{
//		v[vp[end].second] = Max;
//		end++;
//	}
//	return v;
//}
//
////vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) 
////{
////	vector<pair<int, int>> vec;
////	for (int i = 0; i < queries.size(); i++)
////		vec.push_back({ queries[i], i });
////	sort(vec.begin(), vec.end());
////	sort(items.begin(), items.end());
////	int i = 0, j = 0, mx = 0;
////	vector<int> ans(queries.size());
////	while (i < items.size() && j < vec.size())
////		if (items[i][0] > vec[j].first)
////			ans[vec[j].second] = mx, j++;
////		else
////			mx = max(mx, items[i][1]), i++;
////	while (j < vec.size())
////		ans[vec[j].second] = mx, j++;
////	return ans;
////}
//
//
//int main()
//{
//	vector<vector<int>> vv = { { 1,2 }, { 3,2 }, { 2,4 }, { 5,6 }, { 3,5 } };
//	vector<int> v = { 1,2,3,4,5,6 };
//	vector<int> ret = maximumBeauty(vv, v);
//	for (auto& e : ret)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	/*vector<vector<int>> vv = { { 1,2 }, { 1,2 }, { 1,3 }, { 1,4 } };
//	vector<int> v = { 1 };
//	vector<int> ret = maximumBeauty(vv, v);
//	for (auto& e : ret)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;*/
//
//	/*vector<vector<int>> vv = { { 10,1000 } };
//	vector<int> v = { 5 };
//	vector<int> ret = maximumBeauty(vv, v);
//	for (auto& e : ret)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;*/
//
//	return 0;
//}


//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
//{
//	vector<int> v;
//	int begin1 = 0;
//	int begin2 = 0;
//	while (begin1 < m && begin2 < n)
//	{
//		if (nums1[begin1] < nums2[begin2])
//		{
//			v.push_back(nums1[begin1++]);
//		}
//		else
//		{
//			v.push_back(nums1[begin2++]);
//		}
//	}
//	while (begin1 < m)
//	{
//		v.push_back(nums1[begin1++]);
//	}
//	while (begin2 < n)
//	{
//		v.push_back(nums1[begin2++]);
//	}
//	for (int i = 0; i < m; i++)
//	{
//		nums1[i] = v[i];
//	}
//}
//
//int main()
//{
//	vector<int> v1 = { 1,2,3 };
//
//	vector<int> v2 = { 2,5,6 };
//	merge(v1, 6, v2, 3);
//	for (auto& e : v1)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//	
//	return 0;
//}


//#include<vector>
//#include<iostream>
//
//using namespace std;
//
//int removeElement(vector<int>& nums, int val)
//{
//	int begin = 0, end = 0;
//	int size = nums.size();
//	while (end < size)
//	{
//		if (nums[end] != val)
//		{
//			nums[begin++] = nums[end];
//		}
//		end++;
//	}
//	return begin;
//}
//
//int main()
//{
//	vector<int> v = { 0,1,2,2,3,0,4,2 };
//
//	cout << removeElement(v, 2) << endl;
//
//	return 0;
//}


